// 给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
// 你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。
// 设计一个算法来计算你所能获取的最大利润。
// 返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

// 思路1，贪心算法
// 取最左最小值，取最后最大值，得到的差值就是最大利润
function maxProfit(prices) {
    let res = 0
    let low = Infinity
    for (let i = 0; i < prices.length; i++) {
        low = Math.min(low, prices[i])
        res = Math.max(res, prices[i] - low)        
    }
    return res
}


// 思路2，动态规划
// 1. 确定dp数组含义， `dp[i][0]`,第i天，持有股票所得的最多现金，`dp[i][1]`,第i天，不持有股票所得的最多现金
// 2. 确定递推公式
//     1. `dp[i][0]`，两种情况，第i-1天就持有股票`dp[i-1][0]`，第i天买入股票, `-price[i]`,`dp[i][0] = Math.max(dp[i-1][0], -price[i])`
//     2. `dp[i][1]`, 两种情况，第i-1天就不持有股票`dp[i-1][1]`,第i天卖出股票，`price[i]`, `dp[i][1] = Math.max(dp[i-1][1], price[i] + dp[i-1][0])`
// 3. `dp[0][0] = -price[0]; dp[0][1] = 0`
// 4. 确定遍历顺序，从前到后
// 5. 举例推导

function maxProfit2(prices) {
    let dp = new Array(prices.length).fill(0).map(_ => [-Infinity, -Infinity])
    dp[0][0] = -prices[0]
    dp[0][1] = 0
    for (let i = 1; i < prices.length; i++) {
        dp[i][0] = Math.max(dp[i-1][0], -prices[i])
        dp[i][1] = Math.max(dp[i-1][1], prices[i] + dp[i-1][0])        
    }
    return dp[prices.length - 1][1]
}


// 思路3，动态规划，滚动数组
// `dp[i]`只依赖于于`dp[i-1]`的状态，只需要记录当前的状态和前一天的状态就可以了，可以使用滚动数组来节省空间
// 时间复杂度On，空间复杂度O1

function maxProfit3(prices) {
    let dp = new Array(2).fill(0).map(_ => [-Infinity, -Infinity])
    dp[0][0] = -prices[0]
    dp[1][1] = 0
    for (let i = 1; i < prices.length; i++) {
        dp[i % 2][0] = Math.max(dp[(i-1) % 2][0], -prices[i])
        dp[i % 2][1] = Math.max(dp[(i-1) % 2][1], dp[(i-1) % 2][0] + prices[i])       
    }
    return dp[(prices.length - 1) & 2][1]
}
console.log(maxProfit([7,1,5,3,6,4]))
console.log(maxProfit2([7,1,5,3,6,4]))
console.log(maxProfit3([7,1,5,3,6,4]))